<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title></title>
</head>
<body>
Last time we met, you learned about Thompson's Construction - an algorithm
for building NFAs from regular expressions. I also presented a "starter" implementation
of a basic NFA class in C++. In this article, you'll see the connection between these
two. Namely, I'll demonstrate a complete C++ implementation of Thompson's Construction.<br>
Additionally, you will see how to represent regular expressions with parse trees, and get
acquainted with the code that builds complete NFAs from these regular expressions.
<p>
Note: a lot of code was written for this article, and it's no longer possible to 
paste it completely into the text. So, the code can be found in the attached .zip
file. In the article, I'll present and explain only selected portions.

<h3>Implementing Thompson's Construction</h3>
Thompson's Construction, as you probably remember (If you don't, it
is a good time to skim through the previous article) tells us how to build NFAs 
from trivial regular expressions and then compose them into more complex NFAs. Lets
start with the basics:<p>

<h4>The simplest regular expression</h4>
The simplest regular expression is just some single character, for example <b>a</b>.
The NFA for such a regex is:<br>
<img src="n_a.jpg" border="0" width="308" height="113" alt=""><br>
Here is the implementation:<p>
<pre>
// Builds a basic, single input NFA
//
NFA build_nfa_basic(input in)
{
	NFA basic(2, 0, 1);
	basic.add_trans(0, 1, in);
	
	return basic;
}
</pre>
Just to remind you our NFA implementation: The first line of the function creates a new (with
no transitions yet) NFA of size 2 (that is: with 2 states), and sets state 0 to be the initial state and 
	state 1 to be the final state. The second line adds a transition to the NFA that says "<b>in</b> moves
from state 0 to state 1". That's it - a simple regex, a simple construction procedure.<p>
Note that this procedure suits for the construction of an <b>eps</b> transition as well (it was
presented separately in the last article's discussion of Thompson's Construction).

<h4>Some changes to the NFA class</h4>
As I mentioned already, last article's implementation of a simple NFA class was initial in any sense.
I still wasn't sure what operations I might need, so it was as simple as possible. During the coding 
for this article, I found out that I need some additional operations for our NFA class.<p>
First of all, I need direct access to all its members. Instead of providing get and set accessors (which
I personally dislike), I just made all the members (<tt>size</tt>, <tt>initial</tt>, 
<tt>final</tt> and <tt>trans_table</tt>) public.<p>
Recall what I told you about the internal representation I use inside the NFA class - it's a matrix
representing the transition table of a graph. For each <tt>i</tt> and <tt>j</tt>, 
<tt>trans_table[i][j]</tt> is the input that takes the NFA from state <tt>i</tt> to state <tt>j</tt>.
It's <tt>NONE</tt> if there's no such transition (hence a lot of space is wasted - the matrix 
representation, while fast, is inefficient in memory).<p>
Several new operations were added to the NFA class
for my use in the NFA building functions. Their implementation 
can be found in nfa.cpp (one of the files in the .zip that comes with this article). For now,
try to understand how they work (it's really simple stuff), later you'll see why I needed them
for the implementation of various Thompson Construction stages. It may be useful to have the code
of nfa.cpp open in an editor and to follow the code for the operations while reading these 
explanations. Here they are: 
<ul>
<li><b><tt>append_empty_state</tt></b> - I want to append a new, empty state to the NFA. This state
will have no transitions to it and no transitions from it. If this is the transition table before the
appending (a sample table with size 5 - states 0 to 4):<br>
<img src="table0_4.jpg" border="0" width="183" height="195" alt="">
<br>
Then this is the table after the appending:<br>
<img src="table_append.jpg" border="0" width="205" height="189" alt="">
<br>
The shaded cells are the transitions of the original table (be they empty or not), and the white
cells are the new table cells - containing <tt>NONE</tt>.
<p>
<li><b><tt>shift_states</tt></b> - I want to rename all NFA's states, shifting them "higher"
by some given number. For instance, if I have 5 states numbered 0 - 4, and I want to have 
the same states, just named 2 - 6, I will call <tt>shift_states(2)</tt>, and will get the 
following table:<br>
<img src="table_shifted.jpg" border="0" width="210" height="197" alt="">

<li><b><tt>fill_states</tt></b> - I want to copy the states of some other NFA into the first 
table cells of my NFA. For instance, if I take the shifted table from above, and fill its 
first two states with a new small NFA, I will get (the new NFA's states are sky blue):<br>
<img src="table_filled.jpg" width="215" height="209" border="0" alt=""><br>
Note that using <tt>fill_states</tt> after <tt>shift_states</tt> is not incidental. These
two operations were created to be used together - to concatenate two NFAs. You'll see how
they are employed shortly.
</ul>
Now I'm ready to explain how the more complex operations of Thompson's Construction are 
implemented. I hope you have understood how the operations I demonstrated above work, and
have looked at their source code (a good example of our NFA's internal table manipulation).
You still lack the "feel" of why these operations are needed, but this will soon be mended.
Just understand how they work, for now.

<h4>Implementing alternation: a|b</h4>
Here is the diagram of NFA alternation from the previous article:<br>
<img src="n_or.jpg" border="0" width="501" height="289" alt="">
<br>
Given two NFAs, we must build another one, that includes all the states of both
NFAs, plus additional, unified initial and final states. The function that implements
this in nfa.cpp is <tt>build_nfa_alter</tt>. Take a look at its source code now - it is
well commented and you should be able to follow through all the steps with little 
difficulty. Note the usage of the new NFA operations to complete the task. First, you see
how the NFAs states are shifted to make room for the full NFA. <tt>fill_states</tt> is used
to copy the contents of nfa1 to the unified NFA. Finally, <tt>append_empty_state</tt> is
used to add another state at the end - the new final state.

<h4>Implementing concatenation: ab</h4>
Here is the diagram of NFA concatenation from the previous article:<br>
<img src="n_concat.jpg" border="0" width="441" height="141" alt="">
<br>
Given two NFAs, we must build another one, that includes all the states of both NFAs
(note that nfa1's final and nfa2's initial states are overlapping). The function that 
implements this in nfa.cpp is <tt>build_nfa_concat</tt>. Just as in <tt>build_nfa_alter</tt>,
the new NFA operations are used to construct, step by step, a bigger NFA that contains 
all the needed states of the concatenation.

<h4>Implementing star: a*</h4>
Here is the diagram of the NFA for <b>a*</b> from the previous article:<br>
<img src="n_star.jpg" border="0" width="507" height="219" alt="">
<br>
Although the diagram looks complex, the implementation of this construction is relatively
simple, as you'll see in <tt>build_nfa_star</tt>. There's no need to shift states, because
no two NFAs are joined together. There's only a creation of new initial and final states,
and new <b>eps</b> transitions added to implement the star operation.

<h4>Specialty of NFAs constructed by Thompson's Construction</h4>
You might have observed that all the NFAs constructed by Thompson's Construction have
some very specific behavior. For instance, all the basic building blocks for single
letters are similar, and the rest of the constructions just create new links between
these states to allow for the alternation, concatenation and star operations. 
These NFAs are also special implementation-wise. For instance, note that in my 
NFA implementation, the first state is always the initial, and the last state is 
always final. This is useful in a few operations, if you noted.<p>

<h4>A complete NFA construction implementation</h4>
With these operations implemented, we now have a full NFA construction implementation in nfa.cpp !
For instance, the regex <B>(a|b)*abb</B> can be built as follows:
<pre>
	NFA a = build_nfa_basic('a');
	NFA b = build_nfa_basic('b');

	NFA alt = build_nfa_alter(a, b);
	NFA str = build_nfa_star(alt);
	NFA sa = build_nfa_concat(str, a);
	NFA sab = build_nfa_concat(sa, b);
	NFA sabb = build_nfa_concat(sab, b);
</pre>
With these steps completed, <tt>sabb</tt> is the NFA representing <B>(a|b)*abb</B>. Note
how simple it's to build NFAs this way ! There's no need to specify individual transitions
like we did before. In fact, it's not necessary to understand NFAs at all - just build
the desired regex from its basic blocks, and that's it. 

<h4>Even closer to complete automation...</h4>
Though it has now become much simpler to construct NFAs from regular expressions, it's still
not as automatic as we'd like it to be. One still has to explicitly specify the regex 
structure. A useful representation of structure is an expression tree (the construction
above closely reflects the tree structure):
<br>
<img src="tree.jpg" border="0" width="720" height="540" alt="">
<br>
In this tree: . is concatenation, | is alternation, and * is star. So, the regex <B>(a|b)*abb</B>
is represented here in a tree form, just like an arithmetic expression.<p>
Such trees in the world of parsing and compilation are called expression trees, or parse trees. 
For example,
to implement an infix calculator (one that can calculate, for example: 3*4 + 5), the 
expressions are first turned into parse trees, and then these parse trees are walked to 
make the calculations.<p>
Note, this is, as always, an issue of representation. We have the regex in a textual representation: 
<B>(a|b)*abb</B>, and we want it in NFA representation. Now we're wondering how to turn it from
one representation to the other. My solution is to use an intermediate representation - a parse
tree. Going from a regex to a parse tree is similar to parsing arithmetic expressions, and going 
from a parse tree to a NFA will be now demonstrated, using the Thompson's Construction building 
blocks described in this chapter.

<h4>From a parse tree to a NFA</h4>
A parse tree in our case is just a binary tree, since no operation has more than two arguments.
Concatenation and alternations have two arguments, hence their nodes in the tree have two 
childen. Star has one argument - hence only the left child. Chars are the tree leaves. Take 
a good look at the tree drawn above, you'll see this very clearly.<p>
Take a look at the file regex_parse.cpp that comes with this article. It has a lot in it, but
I'll ask you to focus only on some specific things for now. First, find the definitiong of 
<tt>parse_node</tt>, our parse tree. Here it is:<p>
<pre>
typedef enum {CHR, STAR, ALTER, CONCAT} node_type;


// Parse node
//
struct parse_node
{
	parse_node(node_type type_, char data_, parse_node* left_, parse_node* right_)
	    : type(type_), data(data_), left(left_), right(right_) {}

	node_type type;
	char data;
	parse_node* left;
	parse_node* right;	
};
</pre><p>

This is a completely normal definition of a binary tree node, that contains data and some
type by which it is identified. Let us ignore, for the moment, the question how such trees
are built from regexes (if you're very curious - it's all in regex_parse.cpp), and think
how to build NFAs from such trees. Well, as I already mentioned, it's extremely simple,
since parse tree representation is very natural for regexes. Here is the code of the <tt>
tree_to_nfa</tt> function from regex_parse.cpp:<p>
<pre>
NFA tree_to_nfa(parse_node* tree)
{
	assert(tree);
	
	switch (tree->type)
	{
	case CHR:
		return build_nfa_basic(tree->data);
	case ALTER:
		return build_nfa_alter(tree_to_nfa(tree->left), tree_to_nfa(tree->right));
	case CONCAT:
		return build_nfa_concat(tree_to_nfa(tree->left), tree_to_nfa(tree->right));
	case STAR:
		return build_nfa_star(tree_to_nfa(tree->left));
	default:
		assert(0);
	}
}
</pre><p>
Not much of a rocket science, is it ? The power of recursion and trees allows us to build NFAs
from parse trees in just 18 lines of code... 

<h4>From a regex to a parse tree</h4>
If you've looked on regex_parse.cpp by now, you surely noted that it contains quite
a lot of code, much more than I've show so far. This code is the construction of 
parse trees from actual regexes (strings like <B>(a|b)*abb</B>).
<p>
I really hate to be doing this, but I won't explain how this regex-to-tree code works. This
article series is complicated enough without getting into parsing... So you'll just
have to believe me it works (or study the code - it's there !). Just a little something: 
the parsing technique I employ to turn regexes into parse trees is called Recursive Descent
parsing. It's an exciting topic, and you may want to google for it a little, to understand
what it is.

<h4>We've made a long way...</h4>
Lets see what we have already got: we have the full procedure of taking regular expressions
and turning them into NFAs - automatically ! Our program turns the regexes into parse trees,
walks these parse trees and creates NFAs from them using Thompson's Construction. <p>
To see this in action, compile the files nfa.cpp and regex_parse.cpp together (make sure nfa.h
resides in the same directory). I don't know what system you use, but I do it like this:<p>
<pre>g++ -o regex2nfa regex_parse.cpp nfa.cpp</pre><p>
regex_parse.cpp contains a small main function that takes the first argument and displays the NFA
resulting from it. For instance, running:<p>
<pre>regex2nfa "(a|b)*abb"</pre><p>
Displays:
<p><pre>
This NFA has 11 states: 0 - 10
The initial state is 0
The final state is 10
 
Transition from 0 to 1 on input EPS
Transition from 0 to 7 on input EPS
Transition from 1 to 2 on input EPS
Transition from 1 to 4 on input EPS
Transition from 2 to 3 on input a
Transition from 3 to 6 on input EPS
Transition from 4 to 5 on input b
Transition from 5 to 6 on input EPS
Transition from 6 to 1 on input EPS
Transition from 6 to 7 on input EPS
Transition from 7 to 8 on input a
Transition from 8 to 9 on input b
Transition from 9 to 10 on input b
</pre><p>
Which is, if you recall, exactly the NFA we dutifully crafted by hand for <B>(a|b)*abb</B> in the previous
article. Now, we've got it generated automatically !

<h4>A note about the source code</h4>
Along with this article, comes a .zip file containing all the code. It currently consists of 
3 files: nfa.h, nfa.cpp and regex_parse.cpp (which contains a main() function). All the code,
like all my future code for the series is in the public domain - you may do anything you wish
with it. If you have any problem compiling and running it, feel free to contact me, I'll help.
I'll also be quite happy to get feedback and bug reports.


<p>
<HR>
<P>(C) Copyright by Eli Bendersky, 2003. All rights reserved. 
</P>
</body>
</html>
